package com.shm.leetcode;

/**
 * 307. 区域和检索 - 数组可修改
 * 给你一个数组 nums ，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。
 *
 * 实现 NumArray 类：
 *
 * NumArray(int[] nums) 用整数数组 nums 初始化对象
 * void update(int index, int val) 将 nums[index] 的值更新为 val
 * int sumRange(int left, int right) 返回子数组 nums[left, right] 的总和（即，nums[left] + nums[left + 1], ..., nums[right]）
 *
 *
 * 示例：
 *
 * 输入：
 * ["NumArray", "sumRange", "update", "sumRange"]
 * [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
 * 输出：
 * [null, 9, null, 8]
 *
 * 解释：
 * NumArray numArray = new NumArray([1, 3, 5]);
 * numArray.sumRange(0, 2); // 返回 9 ，sum([1,3,5]) = 9
 * numArray.update(1, 2);   // nums = [1,2,5]
 * numArray.sumRange(0, 2); // 返回 8 ，sum([1,2,5]) = 8
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 3 * 104
 * -100 <= nums[i] <= 100
 * 0 <= index < nums.length
 * -100 <= val <= 100
 * 0 <= left <= right < nums.length
 * 最多调用 3 * 104 次 update 和 sumRange 方法
 */
class NumArrayII {
    int[] tree;
    int n;

    /**
     * 方法三：线段树
     * 算法：
     * 线段树是一种非常灵活的数据结构，它可以用于解决多种范围查询问题，比如在对数时间内从数组中找到最小值、最大值、总和、最大公约数、最小公倍数等。
     *
     *
     *
     * 数组 A[0,1,\ldots,n-1]A[0,1,…,n−1] 的线段树是一个二叉树，其中每个节点都包含数组的一个子范围 [i\ldots j][i…j] 上的聚合信息（最小值、最大值、总和等），其左、右子节点分别包含范围 [i \ldots \frac{i+j}{2}][i…
     * 2
     * i+j
     * ​
     *  ] 和 [\frac{i + j}{2} + 1, j][
     * 2
     * i+j
     * ​
     *  +1,j] 上的信息。
     *
     * 线段树既可以用数组也可以用树来实现。对于数组实现，如果索引 ii 处的元素不是一个叶节点，那么其左子节点和右子节点分别存储在索引为 2i2i 和 2i+12i+1 的元素处。
     *
     * 在上图所给出的示例中，每个叶节点都包含初始的数组元素 {2,4,5,7,8,9}。内部节点包含范围内相应元素的总和 - (11) 是从索引 0 到索引 2 的元素之和。而根节点 (35) 是它的两个子节点 (6) 和 (29) 的和,也是整个数组的和。
     *
     * 线段树可以分为以下三个步骤：
     *
     * 从给定数组构建线段树的预处理步骤。
     * 修改元素时更新线段树。
     * 使用线段树进行区域和检索。
     * 构建线段树 :
     * 我们将使用一种非常有效的自下而上的方法来构建线段树。从上面我们已经知道，如果某个节点 pp 包含范围 [i\ldots j][i…j] 的和，那么其左、右子节点分别包含范围 [i \ldots \frac{i + j}{2}][i…
     * 2
     * i+j
     * ​
     *  ] 和 [\frac{i + j}{2} + 1, j][
     * 2
     * i+j
     * ​
     *  +1,j] 上的和。
     *
     * 因此，为了找到节点 pp 的和，我们需要提前计算其左、右子节点的和。
     *
     * 我们从叶节点开始，用输入数组的元素 a[0,1,\ldots,n-1]a[0,1,…,n−1] 初始化它们。然后我们逐步向上移动到更高一层来计算父节点的和，直到最后到达线段树的根节点。
     *
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/range-sum-query-mutable/solution/qu-yu-he-jian-suo-shu-zu-ke-xiu-gai-by-leetcode/
     * @param nums
     */
    public NumArrayII(int[] nums) {
        n = nums.length;
        tree = new int[2*n];
        buildTree(nums);
    }

    /**
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)。
     * 因为我们在 for 循环的每次迭代中计算一个节点的和。而一个线段树中大约有 2n2n 个节点。
     * 这可以通过以下方式证明：具有 nn 个元素的数组线段树有 nn 个叶节点（数组元素本身）。每一层中的节点数是下面一层中节点数的一半。
     * 因此，如果我们按层对节点数求和，我们将得到：
     * n + n/2 + n/4 + n/8 + \ldots + 1 \approx 2n
     * n+n/2+n/4+n/8+…+1≈2n
     *
     * 空间复杂度：O(n)O(n)，我们用了 2n2n 的额外空间来存储整个线段树。
     *
     * 1.上述代码构建的树应是1棵满二叉树，配图是错的。叶子节点存储原始nums
     * 2.根节点的索引是1
     * 3.左子树节点的索引为偶数  右子树节点的索引为奇数
     * 4.叶子节点的索引范围[n,2n-1]
     *
     * @param nums
     */
    void buildTree(int[] nums){
        for(int i=n,j=0;i<2*n;i++,j++){
            tree[i] = nums[j];
        }
        for(int i=n-1;i>0;i--){
            tree[i] = tree[2*i]+tree[2*i+1];
        }
    }

    /**
     * 更新线段树 :
     * 当我们更新数组中某个索引 ii 处的元素时，我们需要重建线段树，因为一些树节点上的和值也会随之产生变化。我们将再次使用自下而上的方法。首先更新存储 a[i]a[i] 元素的叶节点。从那里我们将一路向上，直到根节点，并用其子节点值的总和来更新每个父节点的值。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(\log n)O(logn)。算法的时间复杂度为 O(\log n)O(logn)，因为有几个树节点的范围包括第 ii 个数组元素，每个层上都有一个。共有 \log(n)log(n) 层。
     * 空间复杂度：O(1)O(1)。
     *
     * @param index
     * @param val
     */
    public void update(int index, int val) {        
        index+=n;
        tree[index] = val;
        while(index>0){
            int left= index;
            int right = index;
            if(index%2==0){
                right=index+1;
            }else{
                left=index-1;
            }
            tree[index/2]=tree[right]+tree[left];
            index/=2;
        }
    }

    /**
     * 区域和检索：
     *
     * 我们可以通过以下方式使用线段树进行区域和检索 [L, R][L,R]：算法保持循环不变：l \le rl≤r 以及已经算出 [L \ldots l][L…l] 和 [r \ldots R][r…R] 的总和，其中 ll 和 rr 分别是计算总和时的左边界和右边界。每次迭代的范围 [l,r][l,r] 都会缩小，直到在算法的大约 log nlogn 次迭代后两个边界相遇为止。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(\log n)O(logn)。因为在算法的每次迭代中，我们会向上移动一层，要么移动到当前节点的父节点，要么移动到父节点的左侧或者右侧的兄弟节点，直到两个边界相交为止。在最坏的情况下，这种情况会在算法进行 \log nlogn 次迭代后发生在根节点。
     * 空间复杂度：O(1)O(1)。
     *
     * @param left
     * @param right
     * @return
     */
    public int sumRange(int left, int right) {
        left+=n;
        right+=n;
        int sum=0;

        while(left<=right){
            if(left%2==1){
                sum+=tree[left];
                left++;
            }
            if(right%2==0){
                sum+=tree[right];
                right--;
            }
            left/=2;
            right/=2;
        }
        return sum;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */